#include <iostream>
#include <vector>
#include <memory>

using namespace std;

class Solution {
public:
    int rob(vector<int>& nums) 
    {
        if (nums.size() == 0)
        {
            return 0;
        }
    // 子问题：
    // f(k) = 偷 [0..k) 房间中的最大金额

    // f(0) = 0
    // f(1) = nums[0]
    // f(k) = max{ rob(k-1), nums[k-1] + rob(k-2) }

        int N = nums.size();
        vector<int> dp(N+1, 0);     //动态数组，有n+1个数值（0 ~n），所有的数值都初始化为0
        dp[0] = 0;              //k = 0的结果
        dp[1] = nums[0];        //k = 1的结果
        for (int k = 2; k <= N; k++) 
        {
            dp[k] = max(dp[k-1], nums[k-1] + dp[k-2]);      //循环求出k = n的结果
        }
        return dp[N];
        
        
    }
};

int main()
{
    Solution solu;
    vector<int> nums = {2, 1, 1, 2};
    cout << solu.rob(nums) << endl;

    return 0;
}